class Solution {
public:
    unordered_set<string> st;
    vector<string> ret;
    int n;
    void dfs(string tmp, int begin, vector<string> &words, string &s)
    {
        if (begin == n)
        {
            if (tmp.back() == ' ') tmp.pop_back();
            ret.push_back(tmp);
            return;
        }
        for (int i = begin + 1; i <= n; i++)
        {
            string sub = s.substr(begin, i - begin);
            cout << "sub:" << sub << endl;
            if (st.count(sub))
            {
                string tmp2 = tmp;
                tmp2 += sub;
                tmp2 += " ";
                dfs(tmp2, i, words, s);
            }
        }
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) 
    {
        for (auto &e : wordDict) 
        {
            st.insert(e);
        }
        n = s.size();

        string tmp;
        dfs(tmp, 0, wordDict, s);
        return ret;
    }
};

class Solution 
{
public:
    int candy(vector<int>& ratings) 
    {
        int n = ratings.size();
        vector<int> dp(n);
        int prev = -1;
        int sum = 1;
        dp[0] = 1;
        for (int i = 1; i < n; i++)
        {
            if (ratings[i] == ratings[i - 1])
            {
                prev = i;
                dp[i] = 1;
                sum += dp[i];
            }
            else if (ratings[i] > ratings[i - 1])
            {
                prev = -1;
                dp[i] = dp[i - 1] + 1;
                cout << "dp[i]" << ":" << dp[i] << endl;
                cout << "sum:" << sum << endl;
                sum += dp[i];
            }
            else if (ratings[i] < ratings[i - 1])
            {
                if (prev == -1)
                {
                    if (dp[i - 1] > 2) prev = i;
                    else prev = i - 1;
                }
                cout << sum << endl;
                if (dp[i - 1] == 1)
                {
                    dp[i] = 1;
                    if (prev >= 1 && ratings[prev] < ratings[prev - 1] && dp[prev] + 1 == dp[prev - 1]) prev = prev - 1;
                    dp[prev] += 1;
                
                    sum += (i - prev + 1);
                }
                else
                {
                    dp[i] = 1;
                    sum += dp[i];
                }
            }
        }

        return sum;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int bitmap = 0;
        int n = nums.size();
        for (int i = 0; i < 32; i++)
        {
            int sum = 0;
            for (int j = 0; j < n; j++)
            {
                if ((nums[j] >> i) & 1 == 1) sum++;   /*说明此时第i个比特位为1， 那么就加上一次*/
            }
            sum %= 3;    //最后的结果模上3， 那么就能得到是否只出现了一次的那个元素的该比特位为1
            bitmap |= (sum << i);
        }
        return bitmap;
    }
};